package cn.initcap.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 单调栈数据结构解决经典下一个最符合元素
 * @author initcap
 * @date Created in 2020/5/1 15:48.
 */
public class NextGreaterElement {

    /**
     * 739.每日气温
     * @param T [73, 74, 75, 71, 69, 72, 76, 73]
     * @return  [1, 1, 4, 2, 1, 1, 0, 0]
     */
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return res;
    }

    public int[] nextGreaterElement(int[] nums) {
        int[] res = new int[nums.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0 ; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }

    /**
     * leetcode 1019
     * @param head
     * @return
     */
    public int[] nextLargerNodes(ListNode head) {
        ListNode move = head;
        List<Integer> valList = new ArrayList<>();
        while (move != null) {
            valList.add(move.val);
            move = move.next;
        }
        int[] res = new int[valList.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = valList.size() - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= valList.get(i)) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(valList.get(i));
        }
        return res;
    }

}
